package Leetcode.树;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName 路径总和III
 * @since: 2023/8/19 09:33
 * @auth: kirito
 * @description:
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，
 * 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，
 * 但是路径方向必须是向下的（只能从父节点到子节点）。
 **/
public class 路径总和III {
//    1.dfs
    public int pathSum(TreeNode root, int targetSum) {
        // 如果根节点为空，返回0
        if (root == null) {
            return 0;
        }
        // 计算以当前根节点为起点的路径和
        int res = rootSum(root, targetSum);
        // 递归计算左子树和右子树中路径和为targetSum的个数，并累加到res中
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        // 返回最终结果
        return res;
    }

    // 计算以当前节点为根节点的路径和为targetSum的个数
    private int rootSum(TreeNode root, int targetSum) {
        // 初始化路径和个数为0
        int res = 0;
        // 如果当前节点为空，直接返回0
        if (root == null) {
            return 0;
        }
        // 获取当前节点的值
        int val = root.val;
        // 如果当前节点的值等于目标和，说明找到了一条路径，路径和个数加1
        if (val == targetSum) {
            res++;
        }
        // 递归求解左子树和右子树中路径和为targetSum减去当前节点值的个数，并累加到res中
        res += rootSum(root.left, targetSum - val);
        res += rootSum(root.right, targetSum - val);
        // 返回以当前节点为根节点的路径和个数
        return res;
    }

//    2.前缀和
    Map<Long, Integer> map = new HashMap<>();
    int ans, t;

    public int pathSum2(TreeNode root, int _t) {
        /*
        * 1.根节点为空  返回0
        * 2.初始化  map（0，1）
        * 3.dfs遍历当前节点与节点的val */
        // 如果根节点为空，返回0
        if (root == null) {
            return 0;
        }
        // 初始化目标和和路径和个数
        t = _t;
        ans = 0;
        // 将初始路径和0的计数放入map中
        map.put(0L, 1);
        // 开始深度优先搜索
        dfs(root, root.val);
        // 返回路径和为目标和的个数
        return ans;
    }

    void dfs(TreeNode root, long val) {
        /*
        * 判断当前节点的值-target 在map中是否有  有则ans+1
        * 更新map  map有val的值就基础上+1，否之添加val，1
        * 递归遍历 左右子树
        * 最后回溯当前val值-1*/
        // 如果map中包含路径和为(val - t)的计数，说明找到了一条路径和为目标和t
        if (map.containsKey(val - t)) {
            ans += map.get(val - t); // 更新路径和个数
        }
        // 更新当前路径和的计数
        map.put(val, map.getOrDefault(val, 0) + 1);
        // 递归处理左子树和右子树
        if (root.left != null) {
            dfs(root.left, val + root.left.val);
        }
        if (root.right != null) {
            dfs(root.right, val + root.right.val);
        }
        // 回溯：恢复当前路径和的计数，以便其他路径使用
        /*
        * 这里是个难点，为什么要-1 回溯
        * 假设只剩最后一个根节点和他的两个节点，先判断左，再右
        * 如果在判断右节点的最后不把右节点+的sum的value-1，
        * 就会被左节点所侦测到，可能会影响判断，能理解意思吧
        * 按道理来说，两个子节点之间是不能相互影响的，所以在最后需要将当前节点的值加玩后-1
        * */
        map.put(val, map.getOrDefault(val, 0) - 1);
    }
}
